1. Field of the Invention
The present invention relates generally to a lightweight authentication method, and more particularly, to an authentication method using minimum resources (circuits, power, etc.) in a resource-constrained device.
2. Description of the Related Art
Authentication is a process of verifying whether an object is genuine, i.e., whether the object is what it declares to be. Often, authentication involves checking whether an entity to be authenticated knows a pre-shared secret key by an authenticating entity. In general, a challenge-response scheme is used in which an authenticating entity transmits a query to an entity to be authenticated and the entity to be authenticated generates and transmits a valid response using a secret key, thus proving that it knows the secret key.
The challenge-response scheme largely uses a public key (or an asymmetric key) encryption system, a secret key (or a symmetric key) encryption system, a Hash function, or a logic operation. However, because a resource-constrained device has a poor computation capability and memory capacity, it cannot use an authentication method requiring complex computations, such as the symmetric/public key encryption system.
Among resource-constrained devices, there is a non-contact identification medium that provides various services including distribution, logistics, stock management, etc., substituting for a conventional barcode system.
In a Radio Frequency IDentification (RFID) system, a reader and an RFID device exchange messages through non-contact RF communication and the reader uses an authentication method to verify whether the RFID is authorized. When needed, the reader and the RFID device use a mutual authentication method.
To avert security problems that the RFID faces and prevent privacy invasion for a user, a number of lightweight authentication methods have been proposed. The security of a mathematical dilemma-based authentication method using logic operations can be proved theoretically because it is based on the Learning Parity with Noise (LPN) problem known to be Nondeterministic Polynomial (NP)-hard.
However, the conventional mathematical dilemma-based authentication method using logic operations is vulnerable to a man-in-the-middle type attack.